/**
 * 每个参数的回调函数
 * @param item 树的每个item
 * @param parent 父级
 * @param index 在这一级中的下标
 * @param level 层级
 */
export type CallBack<T, R> = (item: T, parent: T | null, index: number, level: number) => R

export const otherFields = {
  parent: 'zhixin__parent' // 转list的时候记录父子关系
}

export class TreeUtils<T> {
  private readonly tree: T[]
  private readonly children: string

  constructor(tree: T[], children = 'children') {
    this.tree = tree
    this.children = children
  }

  getResult() {
    return this.tree
  }

  forEach(callBack: CallBack<T, void>): TreeUtils<T> {
    TreeUtils.treeForEach(this.tree, callBack, this.children)
    return new TreeUtils(this.tree, this.children)
  }

  map<R>(callBack: CallBack<T, R>): TreeUtils<R> {
    const result = TreeUtils.treeMap(this.tree, callBack, this.children)
    return new TreeUtils(result, this.children)
  }

  filter(callBack: CallBack<T, boolean>): TreeUtils<T> {
    const result = TreeUtils.treeFilter(this.tree, callBack, this.children)
    return new TreeUtils(result, this.children)
  }

  search(callBack: CallBack<T, boolean>): TreeUtils<T> {
    const result = TreeUtils.treeSearch(this.tree, callBack, this.children)
    return new TreeUtils(result, this.children)
  }

  find(callBack: CallBack<T, boolean>): T | null {
    return TreeUtils.treeFind(this.tree, callBack, this.children)
  }

  static treeForEach<T>(tree: T[], callBack: CallBack<T, void>, children = 'children'): void {
    TreeUtils.treeForEachFindParent(tree, null, callBack, children)
  }

  private static treeForEachFindParent<T>(tree: T[], parent: T | null, callBack: CallBack<T, void>, children = 'children', level = 0): void {
    tree.forEach((i, index) => {
      callBack(i, parent, index, level)
      if (i[children]) {
        TreeUtils.treeForEachFindParent(i[children], i, callBack, children, level + 1)
      }
    })
  }

  static treeMap<T, R>(tree: T[], callBack: CallBack<T, R>, children = 'children'): R[] {
    return TreeUtils.treeMapFindParent(tree, null, callBack, children)
  }

  private static treeMapFindParent<T, R>(tree: T[], parent: T | null, callBack: CallBack<T, R>, children = 'children', level = 0): R[] {
    const result: R[] = []
    tree.forEach((i, index) => {
      const val = callBack(i, parent, index, level)
      if (i[children]) {
        val[children] = TreeUtils.treeMapFindParent(i[children], i, callBack, children, level + 1)
      }
      result.push(val)
    })
    return result
  }

  static treeFind<T>(tree: T[], callBack: CallBack<T, boolean>, children = 'children'): T | null {
    return TreeUtils.treeFindFindParent(tree, null, callBack, children)
  }


  private static treeFindFindParent<T>(tree: T[], parent: T | null, callBack: CallBack<T, boolean>, children = 'children', level = 0): T | null {
    for (let index = 0; index < tree.length; index++) {
      const i = tree[index]
      const val = callBack(i, parent, index, level)
      if (val) {
        return i
      }
      if (i[children]) {
        const find = TreeUtils.treeFindFindParent(i[children], i, callBack, children, level + 1)
        if (find) {
          return find
        }
      }
    }
    return null
  }

  /**
   * 不会保留子项
   * 要保留子项请用treeSearch
   * @param tree
   * @param callBack
   * @param children
   */
  static treeFilter<T>(tree: T[], callBack: CallBack<T, boolean>, children = 'children'): T[] {
    return TreeUtils.treeFilterFindParent(tree, null, callBack, children)
  }

  private static treeFilterFindParent<T>(tree: T[], parent: T | null, callBack: CallBack<T, boolean>, children = 'children', level = 0): T[] {
    return tree.filter((item, index) => {
      const val = callBack(item, parent, index, level)
      if (val) {
        if (item[children]) {
          item[children] = TreeUtils.treeFilterFindParent(item[children], item, callBack, children, level + 1)
        }
        return true
      }
      return false
    })
  }


  /**
   * 过滤保留子项
   * 如果过滤不保留子项请用treeFilter
   * @param tree
   * @param callBack
   * @param children
   */
  static treeSearch<T>(tree: T[], callBack: CallBack<T, boolean>, children = 'children'): T[] {
    return TreeUtils.treeSearchFindParent(tree, null, callBack, children)
  }

  private static treeSearchFindParent<T>(tree: T[], parent: T | null, callBack: CallBack<T, boolean>, children = 'children', level = 0): T[] {
    return tree.filter((item, index) => {
      if (item[children]) {
        item[children] = TreeUtils.treeSearchFindParent(item[children], item, callBack, children, level + 1)
        if (item[children].length) {
          return true
        }
      }
      return callBack(item, parent, index, level)
    })
  }

  toList(recordParent = true): T[] {
    return TreeUtils.toList(this.tree, this.children, recordParent)
  }

  /**
   * 列表转成树，只能反向toList函数出来的list
   * @param list
   * @param children
   */
  public static listToTree<T>(list: T[], children = 'children'): T[] {
    let result: T[] = [];
    const map: Record<string, T> = {};
    for (const node of list) {
      const path = node[otherFields.parent];
      if (typeof path !== 'string') {
        continue; // 跳过无效节点
      }
      map[path] = node;
      const parts = path.split('-');
      const indexStr = parts.pop();
      if (indexStr === undefined) {
        continue; // 路径格式错误
      }
      const index = parseInt(indexStr, 10);
      if (isNaN(index)) {
        continue; // 索引非数字
      }
      const parentPath = parts.join('-');
      if (parentPath === '') {
        // 根节点
        result[index] = node;
      } else {
        const parent = map[parentPath];
        if (parent) {
          if (!parent[children]) {
            parent[children] = [];
          }
          parent[children][index] = node;
        }
        // 父节点不存在时忽略（输入列表不正确）
      }
    }
    result = result.filter(node => node !== undefined);
    TreeUtils.treeForEach(result,(item, parent, index, level)=>{
      delete item[otherFields.parent]
    },children)
    return result
  }

  /**
   * 树形转列表
   * @param tree
   * @param children 子级字段
   * @param recordParent 是否记录父级
   */
  public static toList<T>(tree: T[], children = 'children', recordParent = true): T[] {
    const result: T[] = []
    TreeUtils.treeForEach(tree, (item, parent, index) => {
      if (recordParent) {
        if (parent) {
          item[otherFields.parent] = parent[otherFields.parent] + '-' + index
        } else {
          item[otherFields.parent] = '' + index
        }
      }
      result.push(item)
    }, children)
    return result
  }

  /**
   * 根父节点在第一个，依次排序
   * @param tree
   * @param item
   * @param children
   * @return {*[]}
   */
  public static rootSearchParents<T>(tree: T[], item: T, children = 'children'): T[] {
    return TreeUtils.rootSearchParentsReverse(tree, item, children).reverse()
  }

  /**
   * 根父节点在第一个，依次排序
   * @param item
   */
  rootSearchParents(item: T): T[] {
    return TreeUtils.rootSearchParents(this.tree, item, this.children)
  }

  /**
   * 根父节点在最后一个，依次排序
   * @param tree
   * @param item
   * @param children
   */
  public static rootSearchParentsReverse<T>(tree: T[], item: T, children = 'children'): T[] {
    let result = []
    TreeUtils.treeForEach(tree, (item1, parent, index) => {
      if (item1 === item) {
        if (parent) {
          result.push(parent)
          result.push(...TreeUtils.rootSearchParentsReverse(tree, parent, children))
        }
      }
    }, children)
    return result
  }

  /**
   * 根父节点在最后一个，依次排序
   * @param item
   */
  rootSearchParentsReverse(item: T): T[] {
    return TreeUtils.rootSearchParentsReverse(this.tree, item, this.children)
  }

  public static listUseParentIdToTree<T,R extends T & {children:R[]}>(list:T[],root:R[],parentId = 'parentId',id='id') {
    function getRootChildren(root:R[]) {
      root.forEach((i) => {
        i.children = list.filter(l=>l[parentId] === i[id]) as unknown[] as R[]
        if(i.children.length) {
          getRootChildren(i.children)
        }
      })
    }

    getRootChildren(root)
    return root
  }
}
